package com.yvon.service.demo.algorithm.offer;

import com.yvon.service.demo.algorithm.offer.ext.ListNode;

/**
 * 反转链表
 * 定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
 * https://doocs.gitee.io/leetcode/#/lcof/%E9%9D%A2%E8%AF%95%E9%A2%9824.%20%E5%8F%8D%E8%BD%AC%E9%93%BE%E8%A1%A8/README
 */
public class P24 {
    public static void main(String[] args) {
        Solution solution = new P24().new Solution();
        ListNode<Integer> listNode5 = new ListNode<>(5, null);
        ListNode<Integer> listNode4 = new ListNode<>(4, listNode5);
        ListNode<Integer> listNode3 = new ListNode<>(3, listNode4);
        ListNode<Integer> listNode2 = new ListNode<>(2, listNode3);
        ListNode<Integer> listNode1 = new ListNode<>(1, listNode2);
        ListNode<Integer> head = new ListNode<>(0, listNode1);
        ListNode<Integer> integerListNode = solution.reverseList(head);
        ListNode.printLinkedList(integerListNode);
    }


    class Solution {
        /**
         * 原地反转
         */
        public ListNode<Integer> reverseList(ListNode<Integer> head) {
            ListNode<Integer> pre = null;
            ListNode<Integer> cur = head;
            while (cur != null) {
                // 当前节点的下一个指针 临时保存到 t 中
                ListNode<Integer> k = cur.next;
                // 改变当前节点的写一个指针指向前一个节点
                cur.next = pre;
                // 前一个节点指向当前节点(向前走)
                pre = cur;
                // 当前节点往前走
                cur = k;
            }
            return pre;
        }

        /**
         * 递归反转
         */
        public ListNode<Integer> reverseList1(ListNode<Integer> head) {
            if (head == null || head.next == null) {
                return head;
            }
            ListNode<Integer> temp = reverseList1(head.next);
            head.next.next = head;
            temp.next = null;
            return temp;
        }
    }

}
